The original proposal for public key cryptography (W. Diffie and M. E. Hellman, "New directions in cryptography", IEEE Trans. Information Theory, Vol. IT-22, pp. 644-654, November 1976.) was based on the notion of trapdoor permutations, i.e., invertible functions which are easy to compute but apparently difficult to invert, unless some trapdoor information (which makes the inversion easy) is known. The best known implementation of this idea is the RSA scheme, Rivest (Shamir and Adleman, "A method for obtaining digital signatures and public key cryptosystems", Communications of the ACM, Vol. 21, No. 2, pp. 120-126, February 1978) which can solve in a unified way the problems of key management, secure transmission, user identification, message authentication, and digital signatures. In one of the variants of this scheme, the encryption function is the low degree polynomial f(x)=x.sup.3 (mod n) where n is the public product of two secret primes p and q. This function can be efficiently computed with two modular multiplications. Unfortunately, the inverse function f.sup.-1 (x)=x.sup.d (mod n) is a very high degree polynomial, and thus its evaluation is quite slow (especially in software implementations).
In spite of extensive research in the last 16 years, there had been no fundamentally new constructions of trapdoor permutations. To overcome this difficulty, researchers have developed specialized solutions to various cryptographic needs which are not based on this unifying notion. For example, Diffie and Hellman [1976]proposed a key management scheme which is based on the one way permutation of exponentiation modulo a prime. Since this function cannot be efficiently inverted, it is neither an encryption nor a signature scheme. The cryptosystem of Merkle and Hellman (R. C. Merkle and M. E. Hallman, "Hiding information and signatures in trapdoor knapsacks", IEEE Trans. Information Theory, Vol. IT-24, pp. 525-530, September 1978.) is invertible, but its mapping is not onto and thus it can not generate digital signatures. The Fiat-Shamir (Fiat and Shamir, "How to prove yourself: practical solutions to identification and signature problems", Proc. Crypto 86, pp. 186-194August 1986.) and DSS ("DSS: specifications of a digital signature algorithm", National Institute of Standards and Technology, Draft, August 1991.) signature schemes are not one-to-one mappings, and thus they can not be used as cryptosystems.
A natural approach to the construction of efficient trapdoor permutations is to find low degree algebraic mappings (polynomials or rational functions) whose inverses are also low degree algebraic mappings. Such mappings are called birational functions. We are particularly interested in multivariate mappings f(x.sub.1, . . . , x.sub.k)=(v.sub.1, . . . , v.sub.k) in which the x.sub.i and the v.sub.i are numbers modulo a large n=pq, since the solution of general algerbraic equations of this type is at least as hard as the factorization of the modulus. In this context, we say that a polynomial is low degree if its degree is a constant which does not grow with n, and a rational function is low degree if it is the ratio of two low degree polynomials. For example, in the case of cubic RSA, the function is considered low degree, but its inverse is not. General algebraic mappings do not usually have unique inverses, when they do have inverses they usually cannot be written in closed form, and when the closed forms exist they are usually based on root extractions (radicals) or exponentiations whose computation modulo a large n is very slow. The construction of good birational mappings is thus a non-trivial task.
One attempt to construct birational permutations was reported in Fell and Diffie (H. Fell and W. Diffie, "Analysis of a public key approach based on polynomial substitution", Proceedings of Crypto 1985, pp. 340-349.). It used the following DES-like idea:
Let (x.sub.1,x.sub.2, . . . , x.sub.k) be an initial k-vector of variables, and let g(x.sub.2, . . . , x.sub.k) be a secret multivariate polynomial. Alternately replace the current k-vector of multivariate polynomials (p.sub.1,p.sub.2, . . . , p.sub.k) by (p.sub.1 +g(p.sub.2, . . . p.sub.k),p.sub.2, . . . , p.sub.k), and rotate the k-vector to the right. After sufficiently many iterations, expand and publish the resultant k-vector of multivariate polynomials as your public key. The function f is evaluated on input (a.sub.1, a.sub.2, . . . ,a.sub.k) by substituting the a.sub.i 's into the x.sub.i 's in the k published multivariate polynomials, and computing their values (b.sub.1, b.sub.2, . . .,b.sub.k). When the trapdoor information g is known, the inverse of f can be computed by undoing the transformations (i.e., by alternately subtracting g(p.sub.2, . . . ,p.sub.k) from p.sub.1 and rotating the k-vector to the left). Unfortunately, even when g is a quadratic function, the number of terms can be squared in each iteration, and thus the size of the public key can grow double exponentially with the number of iterations, which cannot be too small for security reasons. As the authors themselves conclude, "there seems to be no way to build such a system that is both secure and has a public key of practical size".
A different approach was taken in Shamir (Shamir [1992] is: "Fast signature scheme based on sequentially linearized equations" patent application Ser. No. 07/974,751, filed Nov. 13, 1992, U.S. Pat. No. 5,263,085granted Nov. 16, 1993.). Its basic idea is to use k triangular polynomials g.sub.i (y.sub.1, . . . , y.sub.i), i=1, . . . k of degree two in which the last variable y.sub.i in each polynomial gi occurs linearly. The algebraic mapping (v.sub.1, . . . , v.sub.k)=g(y.sub.1, . . . . , y.sub.k) k-tuples of numbers modulo n defined by the equations v.sub.i =g.sub.i (y.sub.1, . . . , y.sub.i) (mod n), i=1, . . . , k is easy to evaluate since the g.sub.i 's are low degree polynomials. The inverse of the mapping for a given k-tuple (v.sub.1, . . . , v.sub.k) is also easy to compute since the equations are sequentially linearizable: If we already know y.sub.1, . . . , y.sub.i-1, we can substitute them into the equation v.sub.i =g.sub.i (y.sub.1, . . . , y.sub.i) (mod n), and get a linear equation in the single remaining variable y.sub.i which is easy to solve. To hide the obvious triangular shape of the equations, we use a random linear transformation y=AX (mod n) which replaces each y.sub.j in each g.sub.i by some linear combination of x.sub.1, . . . , x.sub.k. The resultant polynomials f.sub.i (x1, . . . , x.sub.k) look like general quadratic polynomials, except the first f.sub.1 which remains linear. The mapping from (x.sub.1, . . . , x.sub.k) to (v.sub.1, . . . , v.sub.k) in which v.sub.i =f.sub.i (x.sub.1, . . . , x.sub.k) (mod n) for i=1, . . . , k, is thus a birational permutation f.
Birational permutations cannot be used in a direct way as public key cryptosystems due to the following generic attack: If f is known, the cryptanalyst can prepare a large number of input-output pairs for this function. Since f is invertible, these pairs (in reverse order) can be used to interpolate the unknown low-degree function f.sup.-1 by solving a small number of linear equations relating its coefficients. This attack discouraged the serious study of cryptographic birational permutations in the literature.